package 剑指offer;

public class _47礼物的最大价值 {
    /**
     * 状态定义：设动态规划矩阵 dp，dp(i,j)代表从棋盘的左上角开始，到达
     *          单元格(i,j)时能拿到礼物的最大值
     * 转移方程：
     *        1.dp(i,j) = grid(i,j)               ,i=0,j=0
     *        2.dp(i,j) = grid(i,j)+dp(i,j-1)     ,i=0,
     *        3.dp(i,j) = grid(i,j)+dp(i-1,j)
     *        4.grid(i,j) + max[dp(i-1,j),dp(i,j-1)]
     * 初始状态：
     *        dp[0][0] = grid[0][0]
     * 返回值：
     *        dp[m-1][n-1]
     */
    public int maxValue(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(i == 0 && j == 0) {
                    continue;
                } else if(i == 0){
                    grid[i][j] = grid[i][j] + grid[i][j-1];
                } else if(j == 0) {
                    grid[i][j] = grid[i-1][j] + grid[i][j];
                } else {
                    grid[i][j] = Math.max(grid[i-1][j], grid[i][j-1]) + grid[i][j];
                }

            }
        }
        return grid[m-1][n-1];
    }
}
